Digital compression has become ubiquitous and has been used in a wide variety of applications (such as video and audio applications). When looking to image capture (i.e., photography) as an example, an image sensor (i.e., charged-coupled device or CCD) is employed to generate analog image data, and an ADC is used to convert this analog image to a digital representation. This type of digital representation (which is raw data) can consume a huge amount of storage space, so an algorithm is employed to compress the raw (digital) image into a more compact format (i.e., Joint Photographic Experts Group or JPEG). By performing the compression after the image has been captured and converted to a digital representation, energy (i.e., battery life) is wasted. This type of loss is true for nearly every application in which data compression is employed.
Compressive sensing is an emerging field that attempts to prevent the losses associated with data compression and improve efficiency overall. Compressive sensing looks to perform the compression before or during capture, before energy is wasted. To accomplish this, one should look to adjusting the theory under which the ADCs operate, since the majority of the losses are due to the data conversion. For ADCs to perform properly under conventional theories, the ADCs should sample at twice the highest rate of the analog input signal (i.e., audio signal), which is commonly referred to as the Shannon-Nyquist rate or Nyquist frequency. Compressive sensing should allow for a sampling rate well-below the Shannon-Nyquist rate so long as the signal of interest is sparse in some arbitrary representing domain and sampled or sensed in a domain which is incoherent with respect to the representation domain.
As is apparent, a portion of compressive sensing is devoted to reconstruction (usually in the digital domain) after resolution; an example of which is described below with respect to a successive approximation register (SAR) ADC and in Luo et al., “Compressive Sampling with a Successive Approximation ADC Architecture,” 2011 Intl. Conf. on Acoustic Speech and Signal Processing (ICASSP), pp 2590-2593. For the compressive sensing framework, a signal {right arrow over (y)} can be expressed as:{right arrow over (y)}= Φ Ψ{right arrow over (α)}= A{right arrow over (α)},  (1)where {right arrow over (α)} (which satisfies the condition {right arrow over (α)}εN) is a frequency sparse signal, Ψ is the inverse fast Fourier transform or IFFT basis matrix (which maps frequency sparse signal {right arrow over (α)} to the time domain), Φ is a row restriction of the identity matrix that provides M samples from a random set Ω (or Φ= I|ΩεM×N), and A is a measurement matrix. The measurement=matrix A should obey the restricted isometry property (RIP) with high probability as long as the number of measurements or samples M is sufficiently large. With a SAR ADC having J stages, the total error em is:em=et+eq,  (2)where eq is the quantization error and et is the truncation error when stopping at m stages. The quantization error eq lies with the range of −VREF/2J and VREF/2J, where VREF is a reference voltage, while the truncation error et lies between 0 and
            2              J        -        m        -        1                    2      J        ⁢            V      REF        .  Thus, from equation (2) above, the total error em becomes:
                              e          m                ∈                  [                                                                      -                  1                                                  2                  J                                            ⁢                              V                REF                                      ,                                                            2                                      J                    -                    m                                                                    2                  J                                            ⁢                              V                REF                                              ]                                    (        3        )            
Using the upper and lower bounds of the total error et, the difference between an analog signal y and quantized samples yq is between these bounds, which means (using equation (1) above) that the input signal can be recovered solving:min|{right arrow over (α)}|0  (4)subject to| W({right arrow over (y)}− A{right arrow over (α)})∥2≦√{square root over (M)}  (5)where W is a diagonal weighting matrix with Wii=1/ei and ei is the maximal quantization error. The purpose of the weighting matrix W is to steer reconstruction towards a solution that agrees more closely with high precision samples rather than low precision samples. This solution (which is usually referred to as a quadratically constrained linear program) under many circumstances may be adequate, but, for other situations, more accuracy may be necessary. Therefore, there is a need for a more accurate reconstruction methodology or algorithm.
Some conventional circuits and systems are: U.S. Pat. No. 7,324,036; U.S. Pat. No. 7,834,795; Laska et al., “Theory and Implementation of an Analog-to-Information Converter Using Random Demodulation,” IEEE Intl. Symposium on Circuits and Systems, May 27-30, 2007, pp. 1959-1962; Meng et al., “Sampling Rate Reduction for 60 GHz UWB Communication Using Compressive Sensing,” Asilomar Conference on Signals, Systems & Computers, 2009; Benjamin Scott Boggess, “Compressive Sensing Using Random Demodulation” (Master's Thesis), 2009; Candes et al., “An Introduction to Compressive Sensing,” IEEE SP Magazine, March 2008; Tropp et al., “Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals”, IEEE Transactions on Information Theory, January 2010; Chen et al., “A Sub-Nyquist Rate Sampling Receiver Exploiting Compressive Sensing”, IEEE Transactions on Circuits and Systemes-I, Reg. Papers, March 2011; R. Baraniuk, “Compressive sensing,” Lecture notes in IEEE Signal Processing Magazine, 24(4):118-120, 2007; Y. Eldar, “Compressed sensing for analog signals,” IEEE Trans. Signal Proc., 2008. submitted; Luo et al., “Compressive Sampling with a Successive Approximation ADC Architecture,” 2011 Intl. Conf. on Acoustic Speech and Signal Processing (ICASSP), pp 2590-2593; Mishali et al., “Blind multi-band signal reconstruction: Compressed sensing for analog signals” IEEE Trans. Signal Proc., 2007. submitted; Rudelson et al., “On sparse reconstruction from Fourier and Gaussian measurements,” Communications on Pure and Applied Mathematics, 61(8):1025-1045, 2008; J. Tropp, M. B. Wakin, M. F. Duarte, D. Baron, and R. G. Baraniuk. Random Filters for compressive sampling and reconstruction,” IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), volume III, pages 872-875, Toulouse, France, May 2006. submitted; van den Berg et al., “SPGL1: A solver for large-scale sparse reconstruction,” June 2007, http://www.cs.ubc.ca/labs/scl/spgl1; and van den Berg et al. “Probing the pareto frontier for basis pursuit solutions,” SIAM Journal on Scientifc Computing, 31(2):890-912, 2008.